1. Field of the Invention
The present invention relates generally to network communications, such as communications in wireless ad-hoc networks. More particularly, the present invention relates to a method, system and apparatus for transmitting messages to radio-silent nodes in a wireless network.
2. Related Art
In wireless ad-hoc networks, all network nodes are preferably equipped with communications transceivers. At least some of these nodes are capable of network routing functions (“routers”); other nodes are sources or destinations for data traffic (“endpoints”). Preferably, all nodes in an ad-hoc network execute a set of known algorithms, and perform a set of known networking protocols. As will be appreciated by those skilled in the art, these algorithms and protocols enable the nodes to find each other, determine paths through the network for data traffic from source to destination(s), and detect and repair ruptures in the network as nodes move, as they fail, as battery power changes, as communications path characteristics change over time, and so forth. Wireless ad-hoc networks do not rely on immobile base stations or other fixed infrastructure. Accordingly, ad-hoc networks are important in military, emergency, mobile and temporary environments (e.g., business meetings, campaign headquarters, and so forth).
FIG. 1a illustrates an example of a wireless ad-hoc network. In FIG. 1a, the circles represent nodes in the network. The solid lines between nodes represent “neighbor relations,” e.g., a communications link connecting two nodes that are capable of forwarding messages (“traffic”) between one another. A given node such as node X has a limit to its communications range (e.g., a radio range or other wireless communications range, such as infrared or laser). A communications range limit for node X is illustrated in FIG. 1a as a dashed circle. In practice, a communications range does not necessarily have, and indeed seldom will have, have a circular pattern or shape. As will be appreciated by one skilled in the art, the actual shape depends on the terrain, propagation patterns, reflections from nearby buildings and/or vehicles, and so forth. FIG. 1a also shows node X's actual neighbors (nodes A1 through A3) and potential neighbors (P1 through P3). Actual neighbors are nodes with whom node X has a communications link or other neighbor relations. Potential neighbors are nodes within X's transmission range that could be used for forwarding messages, but which are not currently being so used.
Other forms of ad-hoc wireless networks simplify routing and minimize routing traffic by organizing nodes (e.g., network members) into hierarchical groups called clusters, with each cluster having a cluster head. A cluster may include a single cluster head and zero or more cluster members. A cluster head serves as a router for affiliated cluster members. Cluster head stations communicate with each other to form a network backbone, and cluster member stations relay messages to the network through affiliated cluster heads. In mobile systems, cluster members move into and out of clusters depending on their physical location and radio connectivity. An example of this type of mobile communications network is shown in FIG. 1b, in which areas 1a, 1b and 1c represent individual clusters. In FIG. 1b, a double-circle indicates a cluster head (“CH”), whereas a single circle indicates a cluster member (“CM”). In the FIG. 1b example, CM2 and CM3 are affiliated with a cluster headed by CH1, and CM6 and CM7 are affiliated with a cluster headed by CH5. CH4 is the head of its own cluster and does not have any affiliated cluster members.
Another example of a mobile communications network is disclosed in U.S. Pat. No. 5,850,592, issued to S. Ramanathan on Dec. 15, 1998, and assigned to the same assignee of the present application. The U.S. Pat. No. 5,850,592 patent discloses a method for a plurality of mobile stations to automatically organize themselves into a hierarchical network, in which some of the stations operate as message gateways for a cluster of mobile stations. Initially, mobile stations search for available cluster heads and initiate an affiliation procedure to establish themselves as cluster members. If the affiliation procedure is successful, a mobile station operates as a cluster member. Otherwise, a mobile station promotes itself to operate as a cluster head.
In the arrangement of the U.S. Pat. No. 5,850,592 patent, each station operates in at least two basic modes. In the first mode, the mobile station serves as a message gateway or router for a cluster of other member stations. The second mode allows the mobile station to operate as a non-gateway (or “cluster member”) station. Each mobile station determines which out of the two modes to operate in, as discussed above. The mobile stations disclosed in the U.S. Pat. No. 5,850,592 patent can operate at two different power levels. When there are no other available cluster heads, a mobile station operates as a cluster head, and transmits at a relatively high power level for communication among other cluster head stations. Although a cluster head communicates at a higher power level with other cluster heads, a cluster head can still communicate with its cluster members using a relatively lower power level.
Nodes in ad-hoc networks employ known routing techniques to accomplish their routing requirements. For example, “link-state” routing is one well-known routing mechanism. In a link-state routing system, each router preferably maintains a link-state database. The database maintains a picture, or dynamic map, of the network including various connections, members, components, etc. Routers generate forwarding or routing tables to direct routing traffic through the network based on information contained in the database. Each router (and/or endpoint) preferably generates updates to the link-state database. An update can contain information regarding a router's neighbors, potential neighbors, link metric data (e.g., a “cost” of transmissions or links), affiliated nodes, network conditions, partition information, etc. A known “flooding” procedure is used to distribute (e.g., flood) these updates throughout the network. One known flooding algorithm is discussed in Chapter 5 of “Routing in Communications Networks,” M. Steenstrup, ed., 1995. Of course, there are many other known flooding procedures.
One example of a link-state routing approach is discussed in U.S. Pat. No. 6,028,857, issued to R. Poor on Feb. 22, 2000, and assigned to the Massachusetts Institute of Technology. According to the U.S. Pat. No. 6,028,857 patent, in a “link-state” routing approach, each network node maintains a routing table (or database) that specifies an “optimal” path toward each network destination. In the U.S. Pat. No. 6,028,857 patent, the term “optimal” is used to generally mean the shortest path, but may account for other factors such as load balancing. As will be appreciated by those skilled in the art, a shortest-path calculation can be performed via a shortest-path first algorithm, for example, Dijkstra's algorithm as explained in Chapter 5 of “Routing in Communications Networks,” M. Steenstrup, ed., 1995.
As discussed in the U.S. Pat. No. 6,028,857 patent, when a node in a link-state routing system transmits a message to a destination node, it first fetches from a routing table an entry for the specified destination. The routing table entry specifies which neighbor of an originating node should relay the message and the identification of that neighbor is installed in a message header as the recipient. The originating node then transmits the message. Many of the originating node's nearby neighbors receive the message, since radio frequency (“RF”) transmissions are essentially omni-directional. However, of all the neighbors that receive the transmission, only the specified recipient acts on the message. The recipient relays the message in the same manner, according to an entry in its routing table corresponding to the destination node. This process continues until the message reaches its ultimate destination. The nodes discussed in the U.S. Pat. No. 6,028,857 patent do not, however, maintain these types of routing tables, but rather maintain “cost tables” that indicate the costs of transmission to other nodes in the network.
Multicast forwarding and routing procedures are also well known in the communication arts. As will be appreciated by those skilled in the art, in a multicast routing scheme, a message (or packet) is routed from a source node to a well-defined group of destination nodes. Typically, an originating source node constructs a routing tree between itself and the group members. Extraneous tree branches are pruned to ensure that packets are not routed further than they need to be.
As will be appreciated by those skilled in the art, the Internet Engineering Task Force (IETF) has established standards for the well-known Internet multicast routing protocols such as Multicast Open Shortest Path First (MOSPF), Distance Vector Multicast Routing Protocol (DVMRP), Protocol Independent Multicast—Sparse Mode (PIM-SM), and Protocol Independent Multicast—Dense Mode (PIM-DM). Similarly, additional types of multicast routing schemes, sometimes known as point-to-multi-point, are accommodated by the well known ATM routing protocol “Private Network to Network Interface” (PNNI) as codified by the ATM Forum. Because multicast routing is well known in the art, it will not now be described in further detail. However, further reference regarding multicast routing schemes may be had to Chapter 5 of “Routing in Communications Networks,” M. Steenstrup, ed., 1995; Chapter 9 of “Interconnections: Bridges and Routers,” R. Perlman, 1992; and Chapters 1, 3 and 8 of “Multicast Networking and Applications,” C. K. Miller 1999.
As will also be understood by those skilled in the art, there are many other known procedures for routing messages over a network, even when a configuration of the network may change, and many procedures for measuring or rating the connectivity of a network in a particular configuration, all of which are well known in the art. Because these techniques are known in the art, they will not now be described in further detail. However, reference may be had to the following technical articles: “Packet Radio Routing,” by Gregory S. Lauer in Chapter 11 of “Routing in Communication Networks,” ed. Martha E. Steenstrup, Prentice-Hall 1995; “Packet Radio Network Routing Algorithms: A Survey,” by J. Hahn and D. Stolle, IEEE Communications Magazine, Vol. 22, No. 11, November 1984, pp. 41–47; “The Organization of Computer Resources into a Packet Radio Network,” by R. E. Kahn, IEEE Trans. on Communications, Vol. COM-25, No. 1, January 1977, pp. 169–178; “Analysis of Routing Strategies for Packet Radio Networks,” J. Garcia Luna Aceves and N. Shacham, Proc. of the IEEE INFOCOM '85, Washington, D.C., March 1985, 292–302; and “The DARPA Packet Radio Network Protocols,” by J. Jubin and J. Tornow, Proc. of the IEEE, Vol. 75, No. 1, January 1987, pp. 21–32. See also U.S. Pat. Nos. 4,718,002, 5,243,592, 5,850,592, 5,881,246, 5,913,921 and 6,028,857 for the general state of the art in wireless network message routing.
There are also many well-known techniques for determining radio transmission propagation patterns and models that will be appreciated by those skilled in the art. For example, RF propagation analysis can be accomplished by a number of known, industry-standard analytic models, including the CRC-Predict algorithm, the ITU Recommendation 370 Propagation Model, the Longley Rice Point-to-Point Propagation Model, the Lee Propagation Model, and so forth, for generating path loss and signal strength grids. Such models commonly support translation of digital terrain elevation data, as well as clutter and signal strength data, from radio frequency modeling systems. In addition, such models have been tested and measured to be accurate in spectrum allocation used by cellular, PCS, digital radio, and paging technologies. These models generally take digital terrain elevation data, spectrum usage, antenna characteristics, and foliage models as inputs, and produce estimates of RF pathloss as outputs. As such, the models can be used to estimate the amount of power needed to transmit from one geographic location to another along with estimates of the signal quality of the transmission as received at the destination radio. Because these techniques are well known in the art, they will not now be described in further detail. However, further reference regarding RF propagation modeling may be had to Chapters 8–11 of “Introduction to Radio Propagation for Fixed and Mobile Communications,” by J. Doble, 1996; Chapters 1 and 15 of “Radiowave Propagation,” M. P. M Hall ed., respectively by M. P. M. Hall and J. D. Parsons, 1989; and Chapter 6 of “Antennas and Radiowave Propagation,” by R. E. Collin, 1985.
Some ad-hoc networks have nodes that occasionally enter radio silence. A “radio-silent” node can not or will not transmit information over any communications channel (e.g., RF, infrared, laser, etc.). Such radio-silent nodes are very common in tactical networks. A radio transmission in proximity to an enemy force might prove fatal, since it may be detected and give away the node's presence and location. Hence, a node may choose to become radio-silent when it is near an enemy. A radio-silent node can still receive messages from a network. At present, there are no procedures to route messages to such radio-silent nodes in ad-hoc networks. Thus, radio-silent nodes are essentially cut-off from their networks.
These types of problems are not adequately addressed in the art. Thus, there is a need to send messages to such radio-silent nodes with a high degree of reliability. There is a further need to integrate one or more radio-silent nodes into an ad-hoc wireless network, so that they can receive messages from other nodes in the network. There is a further need to estimate and/or determine a location area of a radio-silent node.